package linkedlist;

import datastructure.ListNode;
/**
 * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 */
public class M24_SwapNodesinPairs {
    /**
     * 时间复杂度 O(n) 空间复杂度 O(1)
     */
    public ListNode swapPairs1(ListNode head) {
        // 整个哑巴节点输出就靠它
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        /**
         * [dummyHead]-->[head]-->[1]-->[2]-->[3]-->...-->[x]-->null
         * 
         * prevNode - 当前节点的上一个节点
         * currNode - 当前节点
         * nextNode - 当前节点的下一个节点
         * 交换currNode与nextNode的顺序
         * 
         * [prevNode(dummyHead)]-->[currNode(head)]-->[1]-->[2]-->[3]-->...-->[x]-->null    [nextNode]-->null
         * 更新nextNode的位置
         * [prevNode(dummyHead)]-->[currNode(head)]-->[nextNode(1)]-->[2]-->[3]-->...-->[x]-->null
         * 交换相邻节点
         * [prevNode(dummyHead)]-->[nextNode(1)]-->[currNode(head)]-->[2]-->[3]-->...-->[x]-->null
         * 更新prevNode与curNode的位置
         * [dummyHead]-->[nextNode(1)]-->[prevNode(head)]-->[currNode(2)]-->[3]-->...-->[x]-->null
         * 更新nextNode的位置
         * [dummyHead]-->[1]-->[prevNode(head)]-->[currNode(2)]-->[nextNode(3)]-->...-->[x]-->null
         */
        ListNode prevNode = dummyHead, currNode = head, nextNode = null;
        // 当前链表未交换的节点不足两个保持原顺序
        while (prevNode.next != null && prevNode.next.next != null) {
            // 更新nextNode的位置
            nextNode = currNode.next;
            // 交换相邻节点
            currNode.next = nextNode.next;
            nextNode.next = currNode;
            prevNode.next = nextNode;
            // 更新prevNode与curNode的位置
            prevNode = currNode;
            currNode = currNode.next;
        }
        return dummyHead.next;
    }
    /**
     * 递归法
     * 时间复杂度 O(n) 空间复杂度 O(n)
     */
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs2(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
